/*//////////////////////////

Selction Sort

//////////////////////////*/

public class MySelectionSort {

 

    public static int[] doSelectionSort(int[] arr){

        

        for (int i = 0; i < arr.length - 1; i++)

        {

            int index = i;

            for (int j = i + 1; j < arr.length; j++)

                if (arr[j] < arr[index])

                    index = j;

     

            int smallerNumber = arr[index];

            arr[index] = arr[i];

            arr[i] = smallerNumber;

        }

        return arr;

    }

    

    public static void main(String a[]){

        

        int[] arr1 = {10,34,2,56,7,67,88,42};

        int[] arr2 = doSelectionSort(arr1);

        for(int i:arr2){

            System.out.print(i);

            System.out.print(", ");

        }

    }

}

/*//////////////////////////

Insertion Sort

//////////////////////////*/

 

public class MyInsertionSort {

      

    public static void main(String[] args) {

        

        int[] input = { 4, 2, 9, 6, 23, 12, 34, 0, 1 };

        insertionSort(input);

    }

    

    private static void printNumbers(int[] input) {

        

        for (int i = 0; i < input.length; i++) {

            System.out.print(input[i] + ", ");

        }

        System.out.println("\n");

    }

 

    public static void insertionSort(int array[]) {

        int n = array.length;

        for (int j = 1; j < n; j++) {

            int key = array[j];

            int i = j-1;

            while ( (i > -1) && ( array [i] > key ) ) {

                array [i+1] = array [i];

                i--;

            }

            array[i+1] = key;

            printNumbers(array);

        }

    }

}

 

/*//////////////////////////

Merge Sort

//////////////////////////*/

 

public class MyMergeSort {

   

    private int[] array;

    private int[] tempMergArr;

    private int length;

 

    public static void main(String a[]){

        

        int[] inputArr = {45,23,11,89,77,98,4,28,65,43};

        MyMergeSort mms = new MyMergeSort();

        mms.sort(inputArr);

        for(int i:inputArr){

            System.out.print(i);

            System.out.print(" ");

        }

    }

    

    public void sort(int inputArr[]) {

        this.array = inputArr;

        this.length = inputArr.length;

        this.tempMergArr = new int[length];

        doMergeSort(0, length - 1);

    }

 

    private void doMergeSort(int lowerIndex, int higherIndex) {

        

        if (lowerIndex < higherIndex) {

            int middle = lowerIndex + (higherIndex - lowerIndex) / 2;

            // Below step sorts the left side of the array

            doMergeSort(lowerIndex, middle);

            // Below step sorts the right side of the array

            doMergeSort(middle + 1, higherIndex);

            // Now merge both sides

            mergeParts(lowerIndex, middle, higherIndex);

        }

    }

 

    private void mergeParts(int lowerIndex, int middle, int higherIndex) {

 

        for (int i = lowerIndex; i <= higherIndex; i++) {

            tempMergArr[i] = array[i];

        }

        int i = lowerIndex;

        int j = middle + 1;

        int k = lowerIndex;

        while (i <= middle && j <= higherIndex) {

            if (tempMergArr[i] <= tempMergArr[j]) {

                array[k] = tempMergArr[i];

                i++;

            } else {

                array[k] = tempMergArr[j];

                j++;

            }

            k++;

        }

        while (i <= middle) {

            array[k] = tempMergArr[i];

            k++;

            i++;

        }

 

    }

}